Partition List

Given a linked list and a value x,
partition it such that all nodes less than x come before nodes greater than or equal to x.
You should preserve the original relative order of the nodes in each of the two partitions.
For example,
Given 1->4->3->2->5->2 and x = 3,
return 1->2->2->4->3->5.

题目大意：给定一个链表，和目标值x，将比x小的数字放在链表的左边，大于等于x的数字放在链表的右边，要求不能改变数字在原来链表中的相对顺序

题目难度：Medium

/**
 * Created by gzdaijie on 16/6/4
 * left_h 记录左边的头, right_h 记录右边的头
 * left左边的尾,right右边的尾,最后连接起来即可
 * 时间复杂度O(N)，空间复杂度O(1)
 */
public class Solution {
    public ListNode partition(ListNode head, int x) {
        ListNode left_h, right_h, left, right;
        left_h = left = right = right_h = null;

        while (head != null) {
            if (head.val < x) {
                if (left_h == null) left_h = left = head;
                else left = left.next = head;
            } else {
                if (right_h == null) right_h = right = head;
                else right = right.next = head;
            }
            head = head.next;
        }

        if (left_h == null) return right_h;

        if (right_h != null) {
            right.next = null;
            left.next = right_h;
        }
        return  left_h;
    }
}